package Hot_100;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

//括号生成
public class Hot_100_22 {
    /**
     * 主函数
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        //调用括号生成函数
        List<String> ans = generateParenthesis(n);
        for (String str : ans) {
            System.out.print(str + " ");
        }
    }

    //存结果
    static List<String> ans = new LinkedList<>();

    /**
     * 生成括号函数
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        if (n == 0) return ans;
        //调用回溯函数
        backtrack(n, n, "", ans);
        return ans;
    }

    /**
     * 回溯函数
     *
     * @param left
     * @param right
     * @param track
     * @param ans
     */
    public static void backtrack(int left, int right, String track, List<String> ans) {
        if (left < 0 || right < 0) return;
        // 若左括号剩下的多，说明不合法
        if (left > right) return;
        // 当所有括号都恰好用完时，得到一个合法的括号组合
        if (left == 0 && right == 0) {
            ans.add(track);
        }
        // 尝试放一个左括号
        backtrack(left - 1, right, track + '(', ans);
        // 尝试放一个右括号
        backtrack(left, right - 1, track + ')', ans);
    }
}
//时间复杂度: O(4^n/sqrt(n))
//空间复杂度: O(n)